package practise.alogrithm.gotoSiliconValley.array;

import java.util.Arrays;

/**
 * Find out the a sub array, whose sum is not-less than K, and the elements number is the least number for that condition
 * resolving it by use the partition, similar with the first one, sum the number for every partition, and when the sum is
 * larger than K, recalculate the result, end from the index, but note when the result is less than the result, we can
 * start the next sum from that index, and subtract the value from K.
 * the termination condition is the start equals end
 */
public class TopKII {
    public int[] minSub(int[] array, int k){
        if(array==null){
            throw new IllegalArgumentException();
        }
        int start=0, end =array.length-1;
        PartitionRestult result;

        while(start<end){
           result = partitionSum(array,start,end);
           if(result.getSum()<k){//there, it cannot be equal, as the condition is not-less
               k-=result.getSum();
               start=result.getIndex()+1;//remove all the number in that sum, so we start from index+1
           }
           else {
               end=result.getIndex();
           }

        }

        return Arrays.copyOfRange(array,0,end);
    }

    private PartitionRestult partitionSum(int[] array, int start, int end){
        //order in descendant
        int sum=0;
        int index=start;
        start++;
        while (start<=end){//equal happens when end next to index
            if(array[index]==array[start]){
                sum+=array[index++];
                start++;
            }
            else{
                if(array[index]<array[start]){
                    sum+=array[index];
                    swap(array,index++,start++);
                }
                else{
                    swap(array,start,end--);
                }
            }
        }
        return new PartitionRestult(index,sum);
    }

    private void swap(int[] array, int index1, int index2){
        int temp = array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }
}
class PartitionRestult{
    private Integer index;
    private Integer sum;

    PartitionRestult(Integer index, Integer sum) {
        this.index = index;
        this.sum = sum;
    }

    public Integer getIndex() {
        return index;
    }

    public void setIndex(Integer index) {
        this.index = index;
    }

    public Integer getSum() {
        return sum;
    }

    public void setSum(Integer sum) {
        this.sum = sum;
    }
}
